package game;

import java.util.Arrays;

/**
 * 使用双人船载人，最少需要多少个，限制了船的载重
 *
 * @author Liaorun
 */
public class LeastDoubleBoat {

    public static void main(String[] args) {
        System.out.println(leastDoubleBoat(new int[]{6,7}, 10));
        System.out.println(leastDoubleBoat(new int[]{1, 2, 3, 4, 5}, 10));
        int res = leastDoubleBoat(new int[]{1, 2, 3, 4, 6, 7, 8, 9}, 10);
        int res1 = leastDoubleBoat(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 10);
        int res2 = leastDoubleBoat(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 10);
        System.out.println(res);
        System.out.println(res1);
        System.out.println(res2);
    }


    /**
     * @param mansWeight 乘客的体重
     * @param boatLimit  小船的载重
     * @return 需要船的数量
     */
    public static int leastDoubleBoat(int[] mansWeight, double boatLimit) {

        int max = Integer.MIN_VALUE;
        for (int item : mansWeight) {
            max = Math.max(item, max);
        }
        if (max > boatLimit) {
            // 无解，有人太重了
            return -1;
        }
        Arrays.sort(mansWeight);

        int beginPos = -1;

        // 找到<= limit/2  区域结束的位置
        for (int i = 0; i < mansWeight.length; i++) {
            if (mansWeight[i] > boatLimit / 2) {
                beginPos = i;
                break;
            }
        }


        // 需要船的数量
        double boatCount = 0;
        if (beginPos == -1) {
            // 所有人的体重都小于 limit/2, 那么任意两个人可以一起坐一条小船
            boatCount = mansWeight.length / 2d;
        } else {
            // 存在体重超过 limit/2 的人
            // 双指针从开始为向两边走，两两配对上船
            int left = beginPos - 1, right = beginPos;
            // 较轻的没有配对的人
            int leave = 0;

            while (left >= 0 && right < mansWeight.length) {
                if (mansWeight[left] + mansWeight[right] <= boatLimit) {
                    // 两人可以配对坐一条船
                    boatCount++;
                    left--;
                    right++;
                } else {
                    // 两人加起来太重，找一个更轻的人来配对
                    left--;
                    leave++;
                }
            }

            // 可以一轻一重配对的都配对了,处理较轻的没有船的人，这些人可以两人一艘船
            boatCount += (double) leave / 2;
            // 处理较重的没有船的人，由于没有分到配对的较轻的人，只能一人一艘船
            boatCount += mansWeight.length - right;
        }


        // 向上取整，不满一条船的要一条
        return (int) Math.ceil(boatCount);
    }
}
